package com.base.dynamicprograming;

/**
 * @ClassName UniquePaths
 * @Description 62. 不同路径
 * @Author li
 * Date 2021/8/22 22:45
 * Copyright
 **/
public class UniquePaths {
    public int uniquePaths(int m,int n){
        int[][] f = new int[m][n];
        // 从（0,0）到 （0,0）路径只有一条
        //只有向下，或者向右两种移动方式，所以当前结点的前一个结点，必定是它的左结点或者上结点。
        f[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i>0&&j>0){
                    f[i][j] = f[i-1][j] + f[i][j-1];

                }else if (i>0){
                    f[i][j] = f[i-1][j];
                }else if(j>0){
                    f[i][j] = f[i][j-1];
                }
            }
        }
        return f[m-1][n-1];
    }

    /**
     * 2021/12/13 再一次做，感觉它不是那么难了
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths1(int m, int n) {
        int[][] dp = new int[m][n];
        // 由于规定：机器人只能向右或者向下运动
        // 所以当前状态 可能是由上，由左的状态转移而来
        // dp[i][j] = dp[i][j-1] + dp[i-1][j];
        // 还要考虑特殊情况,也就是矩阵的边界
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(i==0||j==0){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
